package _interview100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 279. 完全平方数
 */
public class No279 {
    private List<Integer> list;
    private int[][] cache;

    public int numSquares(int n) {
        list = new ArrayList<>();
        int i = 1;
        for (; i * i <= n; i++) {
            list.add(i * i);
        }
        int size = list.size();
        cache = new int[size][n + 1];
        return dfs(size - 1, n);
    }

    private int dfs(int i, int c) {
        if (c < 0) return Integer.MAX_VALUE / 2;
        else if (i < 0) return c == 0 ? 0 : Integer.MAX_VALUE / 2;
        else if (cache[i][c] != 0) return cache[i][c];
        else if (c < list.get(i)) return cache[i][c] = dfs(i - 1, c);
        else return cache[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - list.get(i)) + 1);
    }

    public int numSquares2(int n) {
        int size = (int) (Math.pow(n, (double) 1 / 2));

        int[][] f = new int[size + 1][n + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2);
        f[0][0] = 0;
        for (int i = 0; i < size; i++) {
            for (int c = 0; c < n + 1; c++) {
                if (c < (i + 1) * (i + 1)) f[i + 1][c] = f[i][c];
                else f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - (i + 1) * (i + 1)] + 1);
            }
        }
        return f[size][n];
    }

    public int numSquares4(int n) {
        int[] f = new int[n + 2];
        Arrays.fill(f, Integer.MAX_VALUE / 2);
        f[0] = 0;
        for (int i = 0; i * i <= n; i++) {
            for (int c = (i + 1) * (i + 1); c < n + 1; c++) {
                f[c] = Math.min(f[c], f[c - (i + 1) * (i + 1)] + 1);
            }
        }
        return f[n];
    }
}
